#include <iostream>
#include <list>
#include <cstring>
#include <queue>
#define INF 999999
#define NIL -1
using namespace std;
struct Edge
{
    int start;
    int end;
    int length;
    Edge(){}
    Edge(int s,int e,int l){start=s;end=e;length=l;}
    bool operator<(const Edge& e)
    {
        return this->length<e.length;
    }
    friend ostream& operator<<(ostream& out,const Edge& obj)
    {
        out<<obj.start<<"-"<<obj.end<<":"<<obj.length;
        return out;
    }
};

struct PrimStruct
{
    int id;  //点序号
    int pi; //前驱
    int key;//最小边权重
    PrimStruct(){}
    PrimStruct(int v,int p,int k){id=v;pi=p;key=k;}
    bool operator<(const PrimStruct& p) const
    {
        if(this->key>p.key)
            return true;
        else if(this->key==p.key)
            return this->id>p.id;
        return false;
    }
};
//图类,使用邻接矩阵实现
class Graph
{
    private:
        int V;//图包含点数
	    list<Edge> ** adjList;
        list<Edge> * edges;
	public:

        //根据点数构造图
		Graph(int V);

        //析构函数
        ~Graph();
        //根据起点和终点构造一条边
        void addEdge(int start,int end,int weight=1);

        //打印图信息
        void printMap();

        //利用Kruskal算法求出最小生成树边集
        list<Edge> * kruskal();

        //利用Prim算法求出最小生成树边集
        list<Edge> * prim();
};
